package com.ljy.my_study.leetcode.翻转字符串里的单词;

/**
 * @author lijunying
 * @date 2021/11/26 14:40
 */
public class TestMain {

//    给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
//
//    单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
//
//    请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
//
//    说明：
//
//    输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
//    翻转后单词间应当仅用一个空格分隔。
//    翻转后的字符串中不应包含额外的空格。
//             
//
//    示例 1：
//
//    输入：s = "the sky is blue"
//    输出："blue is sky the"
//    示例 2：
//
//    输入：s = "  hello world  "
//    输出："world hello"
//    解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
//    示例 3：
//
//    输入：s = "a good   example"
//    输出："example good a"
//    解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
//    示例 4：
//
//    输入：s = "  Bob    Loves  Alice   "
//    输出："Alice Loves Bob"
//    示例 5：
//
//    输入：s = "Alice does not even like bob"
//    输出："bob like even not does Alice"
//             
//
//    提示：
//
//            1 <= s.length <= 104
//    s 包含英文大小写字母、数字和空格 ' '
//    s 中 至少存在一个 单词
// 
//
//    进阶：
//
//    请尝试使用 O(1) 额外空间复杂度的原地解法。
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/reverse-words-in-a-string
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
//        System.out.println(new TestMain().reverseWords("Alice does not even like bob"));
        System.out.println(new TestMain().reverseWords(" a   good   example "));
    }
//    对s的char数组进行操作
    public String reverseWords(String s) {
        char[] chars=s.toCharArray();
        int len=chars.length;
        int left=0;
        //缩进
        for(int i=0;i<len;i++){
            if(chars[i]!=' '){
                left=i;
                break;
            }
        }
        int right=len-1;
        for(int i=len-1;i>=0;i--){
            if(chars[i]!=' '){
                right=i;
                break;
            }
        }
        len=right+1;
        int start=0;
        for(int i=left;i<len;i++){
            if(chars[i]==' '&&chars[i-1]==' '&&i>0){
                continue;
            }
            chars[start++]=chars[i];
        }
        int end=start>0?start-1:0;
        start=0;
        len=end+1;
        reverse(chars,start,end);
        left=0;
        for(int i=0;i<len;i++){
            if((i>0&&chars[i-1]==' ')||i==0){
                left=i;
            }
            if((i+1<len&&chars[i+1]==' ')||i==len-1){
                reverse(chars,left,i);
                continue;
            }
        }
        return String.valueOf(chars,0,len);
    }

    private void reverse(char[] chars,int start,int end){
        while(start<end){
            char tmp=chars[start];
            chars[start]=chars[end];
            chars[end]=tmp;
            start++;
            end--;
        }
    }
}
